package com.easy.leetcode.listNode;

import java.util.Stack;

/**
 * 430. 扁平化多级双向链表
 */
public class Flatten430 {
    public Node flatten(Node head) {
        //根据题意，优先遍历child,然后遍历next,遇到child时，需用栈把next指针存储起来
        Stack<Node> stack = new Stack<>();
        //tmp 指向头节点，用来遍历
        Node tmp = head;
        //cur 当前节点
        Node cur=head;
        //tmp 不等于null 或者栈不为空，则代表没有遍历完，继续遍历
        while (tmp != null || !stack.isEmpty()) {
            //tmp为空，就从栈中取最近的节点出来，作为tmp
            tmp = tmp == null ? stack.pop() : tmp;
            //非头节点时更新节点指针
            if (tmp!=cur){
                //更新当前节点指针
                cur.next=tmp;
                //更新下一个节点的pre指针
                tmp.prev=cur;
                //重要:将当前节点的child置null,不然是多级链表
                cur.child=null;
                //移动当前节点的指针
                cur=cur.next;
            }
            //当前节点有子节点
            if (tmp.child != null) {
                //next不为空才保存，不加此判断可能会空指针
                if (tmp.next!=null){
                    stack.push(tmp.next);
                }
                tmp = tmp.child;
            } else {
                //没有子节点
                tmp = tmp.next;
            };
        }
        return head;
    }
}

class Node {
    public int val;
    public Node prev;
    public Node next;
    public Node child;
};